﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0119_IncreasingTriplet : IAlgorithm
    {
        // 递增的三元子序列

        // 给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
        // 如果存在这样的三元组下标(i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

        // 提示：
        // 1 <= nums.length <= 5 * 10^5
        // -2^31 <= nums[i] <= 2^31 - 1

        // 进阶：你能实现时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案吗？

        public void Test()
        {
            // 算法参数定义
            var nums = new int[] { 2, 1, 5, 0, 4, 6 };
            // 算法执行与打印
            Console.WriteLine(IncreasingTriplet(nums));
        }

        // 算法
        public bool IncreasingTriplet(int[] nums)
        {
            int a = int.MaxValue, b = int.MaxValue;
            foreach (var item in nums)
                if (item <= a)
                    a = item;
                else if (item <= b)
                    b = item;
                else
                    return true;
            return false;
        }
    }
}
